package LeetCode;

import java.util.HashMap;

public class LC_523_ContinuousSubarraySum {

    public static void main(String[] args) {

    }

    public class Solution {
        public boolean checkSubarraySum(int[] nums, int k) {
            if (nums == null || nums.length < 1) return false;
            int n = nums.length;
            if (k != 0 && n >= (long) 2 * Math.abs(k)) return true;
            HashMap<Integer, Integer> map = new HashMap<>();
            map.put(0, -1);
            int prefixSum = 0;
            for (int i = 0; i < n; i++) {
                prefixSum += nums[i];
                if (k != 0) prefixSum %= k;
                Integer pre = map.get(prefixSum);
                if (pre != null) {
                    if (i - pre > 1) return true;
                } else {
                    map.put(prefixSum, i);
                }
            }
            return false;
        }

    }
}